package com.lili.str;

/**
 * @Auther: 李 力
 * @Date: 2024/8/22
 * @Description: com.lili.str
 * @version: 1.0
 */
public class LeetCode75 {

    public static String minWindow(String s, String t) {
        char[] charArray = s.toCharArray();
        int[] targetCount = new int[128];
        for (char ch : charArray) {
            targetCount[ch]++;
        }
        int passTotal = 0;
        int passed = 0;
        for (int i : targetCount) {
            if (i > 0) {
                passTotal++;
            }
        }
        char[] source = s.toCharArray();
        int[] sourceCount = new int[128];
        int i = 0, j = 0;

        Result result = null;
        while (j < source.length) {
            char right = source[j];
            sourceCount[right]++;
            if (sourceCount[right] == targetCount[right]) {
                passed++;
            }
            while (passed == passTotal && i <= j) {
                if (result == null) {
                    result = new Result(i, j);
                } else {
                    if (j - i < result.j - result.i) {
                        result = new Result(i, j);
                    }
                }
                char left = source[i];
                sourceCount[left]--;
                if (sourceCount[left] < targetCount[left]) {
                    passed--;
                }
                i++;
            }
            j++;
        }
        return result == null ? "" : new String(source, result.i, result.j - result.i + 1);
    }

    static class Result {
        int i;
        int j;

        public Result(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
}
